package ee.homework.sixth;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;

public class OpenAddressing {
	private List<Long> keys;
	private int size = 200;
	private long[] table = new long[size];
	private long p = 1212839;
	private long a = 580180;
	private long b = 733839;
	private int collisionChain = 0;

	public static void main(String[] args) {
		OpenAddressing hf = new OpenAddressing();
		hf.readKeys();
		hf.insertKeys();
	}

	private void insertKeys() {
		for (Long integer : keys) {
			insertKey(integer);
		}
		System.out.println(collisionChain);
	}

	private void insertKey(Long k) {
		int i = 0;
		int j;
		while (i < size) {
			j = (universalHash(k) + i) % size;
			if (table[j] == 0) {
				table[j] = k;
				break;
			} else {
				i++;
			}
		}
		if (i > collisionChain) {
			collisionChain = i;
		}
		if (i == size) {
			System.out.println("hash table overflow");
		}
	}

	private int universalHash(long k) {
		return (int) (((a * k + b) % p) % size);
	}

	private void readKeys() {
		try {
			BufferedReader reader = new BufferedReader(new FileReader(new File(
					"data\\keys.txt")));
			String line = null;
			keys = new ArrayList<Long>();
			while ((line = reader.readLine()) != null) {
				keys.add(Long.parseLong(line.trim()));
			}
		} catch (IOException e) {
			System.out.println("Error occurred while trying to read file: "
					+ e.getMessage());
		}
	}

}
